/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package insertion;

/**
 *插入排序
 * 假设第一个数为已经排好的序列  从第二个开始 按照大小插入前方的有序序列
 * @author root
 */
public class MyInsertion {
    public static int[] myInsertion(int[] a){
        if(a!=null&&a.length>1){
            for(int i=1;i<a.length;i++){
                int tmp=a[i],j=i;
                if(a[j-1]>tmp){
                    while(j>=1&&a[j-1]>tmp){
                        a[j]=a[j-1];
                        j--;
                    }
                }
                a[j] = tmp;
            }
        }
        return a;
    }
    
    public static int[] myInsertion2(int[] a){
        if(a!=null&&a.length>1){
            int tmp = 0,j=0;
            for(int i=1;i<a.length;i++){
                tmp = a[i];
                j=i;
                while(j>=1&&a[j-1]>tmp){
                    a[j]=a[j-1];
                    j--;
                }
                a[j]=tmp;
            }
        }
        return a;
    }
}
